#define _CRT_SECURE_NO_WARNINGS 1
//RR时间片轮转与HPF优先级调度算法
#include<iostream>
#include<queue>
typedef struct {
    char pname;//进程名
    int arrive_t;//到达时间
    int service_t;//服务时间
    int finish_t;//完成时间
    int turnaround_t;//周转时间
    double w_turnaround_t;//带权周转时间
    char state;//进程状态: w：等待， m：就绪，r：运行
    int priority;//优先级
    int run_t;//运行时间
    int remaining_t;//剩余时间
}PCB;
//typedef struct PCB_que {
//    PCB *p;
//    int capacity;
//}PCB_que;
PCB p[20];
int n = 5;
void init()//初始化进程信息：进程名、到达时间、服务时间、状态
{
    p[0].pname = 'A';
    p[0].arrive_t = 0;
    p[0].service_t = 3;
    p[0].priority = 2;

    p[1].pname = 'B';
    p[1].arrive_t = 2;
    p[1].service_t = 5;
    p[1].priority = 1;

    p[2].pname = 'C';
    p[2].arrive_t = 2;
    p[2].service_t = 2;
    p[2].priority = 4;

    p[3].pname = 'D';
    p[3].arrive_t = 4;
    p[3].service_t = 4;
    p[3].priority = 3;

    p[4].pname = 'E';
    p[4].arrive_t = 4;
    p[4].service_t = 1;
    p[4].priority = 5;

    for (int i = 0; i < n; i++)
    {
        p[i].state = 'w';//初始状态都设为等待
        p[i].run_t = 0;
        p[i].remaining_t = p[i].service_t;
    }
}
void original_HPF_P()//输出HPF的初始状态
{
    std::cout << "进程的初始状态" << std::endl;
    std::cout<<"------------------------------------------------------------------"<<std::endl;
    std::cout<<"进程名\t\t到达时间\t服务时间\t优先级(数越大优先级越高)"<<std::endl;
    int i;
    for (i = 0; i < n; i++)
    {
        std::cout << p[i].pname << "\t\t" << p[i].arrive_t << "\t\t" << p[i].service_t << "\t\t" << p[i].priority <<  std::endl;
    }
}
void original_RR_P()//输出时间片轮转调度算法各进程的初始状态
{
    std::cout << "进程的初始状态" << std::endl;
    std::cout<<"------------------------------------------------------------------"<<std::endl;
    std::cout<<"进程名\t\t到达时间\t服务时间"<<std::endl;
    int i;
    for (i = 0; i < n; i++)
    {
        std::cout << p[i].pname << "\t\t" << p[i].arrive_t << "\t\t" << p[i].service_t << std::endl;
    }
}
//HPF非抢占式优先级调度算法
//比较后面的优先级
bool cmp1(PCB a, PCB b)//先按到达时间排序，再按优先级排序
{
    if (a.arrive_t == b.arrive_t)
    {
        return a.priority > b.priority;//数越大，优先级越高
    }
    else
    {
        return a.arrive_t < b.arrive_t;
    }
}
bool cmp2(PCB a, PCB b)//按优先级排序
{
    return a.priority > b.priority;
}

void Print_cur_pro(int i)       //打印当前运行程序
{
    p[i].finish_t = std::max(p[i - 1].finish_t, p[i].arrive_t) + p[i].service_t;//完成时间
    std::cout << "正在执行>" << std::endl;
    std::cout << "--------------------------------------------------------------------------------------------------" << std::endl;
    std::cout << "进程名\t\t到达时间\t服务时间\t完成时间\t周转时间\t带权周转时间" << std::endl;
    p[i].turnaround_t = p[i].finish_t - p[i].arrive_t;//周转时间=完成时间-到达时间
    p[i].w_turnaround_t = (double)p[i].turnaround_t / p[i].service_t;//带权周转时间=周转时间/服务时间
    printf("%c\t\t    %d\t\t    %d\t\t   %d\t\t   %d\t\t  %0.2f\n", p[i].pname, p[i].arrive_t,
        p[i].service_t, p[i].finish_t, p[i].turnaround_t, p[i].w_turnaround_t);
}

void HPF_work()
{
    std::sort(p, p + n, cmp1);//先按到达时间排序，再按优先级排序
    p[0].state = 'r';
    p[0].finish_t = p[0].arrive_t + p[0].service_t;//第一个进程的完成时间=到达时间+服务时间
    Print_cur_pro(0);
    int cnt = 1;//判断完成时间内到达的进程个数,设第一个进程已经到达
    int cout_num = 0;
    std::queue<char>Ready_queue;
    for (int i = 1; i < n; i++)//看每一个进程
    {
        if (cnt < n)
        {
            for (int j = i; j < n; j++)//看后面来的进程
            {
                if (p[j].arrive_t <= p[i - 1].finish_t)//比较到达时间和上一个进程的完成时间
                {
                    cnt++;//如果已经达到就标记
                    Ready_queue.push(p[j].pname);
                    p[j].state = 'm';
                }
                else
                    break;
            }
            std::cout << "就绪队列:" << std::endl;
            int size = Ready_queue.size();
            for (int m = 0; m < size; m++)
            {
                std::cout << Ready_queue.front() << std::endl;
                Ready_queue.pop();
            }
            if (cnt > i)//需要排序时
            {
                std::sort(p + i, p + cnt, cmp2);//按优先级排序
            }
        }
        else if(cnt>=n)
        {
            std::cout << "就绪队列:" << std::endl;
            for (int m=cout_num+1; m < n; m++)
            {
                Ready_queue.push(p[m].pname);
            }
            int size = Ready_queue.size();
            for (int m = 0; m < size; m++)
            {
                std::cout << Ready_queue.front() << std::endl;
                Ready_queue.pop();
            }
        }
        p[i].state = 'r';
        Print_cur_pro(i);
        cout_num++;
    }

    std::cout << "进程执行顺序为：" << std::endl;
    for (int i = 0; i < n; i++)
    {
        std::cout << p[i].pname << " ";
    }
}

bool cmp3(PCB a, PCB b)//按到达时间排序
{
    return a.arrive_t < b.arrive_t;//按到达时间从小到达排序
}
//时间片轮转法,新来的进程应该放在就绪队列的末尾
void RR_work()
{
    int q = 2;//设时间片=2
    //先按到达时间排序
    std::sort(p, p + n, cmp3);//把这些进程编号
    std::queue<int> ready_q;//就绪队列
    ready_q.push(0);//先把第一个来的放到就绪队列
    //如果到达了，就放在就绪队列中，弹出队首元素
    int temp;
    int now_time = p[0].arrive_t;//从第一个进程到达时间开始算
    int cnt = 1;//第一个进程已经处理了，接下来从p[1]开始看。
    int i;
    std::cout<<"进程的执行顺序："<<std::endl;
    while (1)
    {
        if (!ready_q.empty())//如果不空，队列中有元素，就占用处理机，进入运行状态
        {
            temp = ready_q.front();//取队头元素
            std::cout<<p[temp].pname<<" ";
            ready_q.pop();//弹出队首元素
            p[temp].run_t = p[temp].run_t + q;//运行时间
            now_time = now_time + q;
            //按顺序排好序
            while (cnt < n && p[cnt].arrive_t <= now_time)
            {
                ready_q.push(cnt);//放入队尾
                p[cnt].state = 'm';//进入就绪队列
                cnt++;//等待下一个进程的到达
            }
            if (p[temp].run_t < p[temp].service_t)//如果这个进程还没有运行完成，就放到队列尾部
            {

                p[temp].remaining_t = p[temp].service_t - p[temp].run_t;//剩余时间=需要的服务时间-已经运行的时间

                ready_q.push(temp);//当前的这个再次入队，放在队尾
                p[temp].state = 'm';//状态为就绪态
            }
            else
            {
                now_time = now_time - (p[temp].run_t - p[temp].service_t);
                p[temp].state = 'f';//已经执行完了
                p[temp].finish_t = now_time;
            }
        }
        for (i = 0; i < n; i++)
        {
            if (p[i].state == 'm' || p[i].state == 'w')//如果还有进程是等待或者就绪态，就继续进行时间片轮转
                break;
        }
        if (i == n)//如果都执行完了
            break;
    }
}
bool cmp4(PCB a, PCB b)
{
    return a.pname < b.pname;//按进程名从小到达排序
}
void Print()
{
    int i;
    std::cout<<std::endl;
    std::sort(p, p + n, cmp4);
    std::cout<<"--------------------------------------------------------------------------------------------------"<<std::endl;
    std::cout<<"进程名\t\t到达时间\t服务时间\t完成时间\t周转时间\t带权周转时间"<<std::endl;
    int sum_t1 = 0;//代表总的周转时间
    double sum_t2 = 0;//代表总的带权周转时间
    for (i = 0; i < n; i++)
    {
        p[i].turnaround_t = p[i].finish_t - p[i].arrive_t;//周转时间=完成时间-到达时间
        p[i].w_turnaround_t = (double)p[i].turnaround_t / p[i].service_t;//带权周转时间=周转时间/服务时间
        sum_t1 = sum_t1 + p[i].turnaround_t;
        sum_t2 = sum_t2 + p[i].w_turnaround_t;
        printf("%c\t\t    %d\t\t    %d\t\t   %d\t\t   %d\t\t  %0.2f\n", p[i].pname, p[i].arrive_t,
            p[i].service_t, p[i].finish_t, p[i].turnaround_t, p[i].w_turnaround_t);

    }
    printf("平均周转时间:%0.2f\n", (double)sum_t1 / n);
    printf("平均带权周转时间:%0.2f\n", (double)sum_t2 / n);

}

void menu() 
{
    std::cout<<"\t\t\t"<< "<< -------------- 操作系统进程调度算法模拟程序----------—— >>"<<std::endl;
    std::cout<<"\t\t\t"<<"1.高优先级算法"<<std::endl;
    std::cout<<"\t\t\t"<<"2.时间片轮转算法"<<std::endl;
    std::cout<<"\t\t\t"<<"0.退出"<<std::endl;
 }

int main()
{

    int input = 0;
    do {
        menu();
        std::cout << "\t\t\t" << "请选择进程调度算法:";
        std::cin>>input;
        switch (input)
        {
        case 1:
            init();
            original_HPF_P();
            HPF_work();
            Print();
            break;
        case 2:
            init();
            original_RR_P();
            RR_work();
            Print();
            break;
        case 0:
            printf("感谢您的使用\n");
            break;
        default:
            printf("请重新选择\n");
        }
    } while (input);

    return 0;
}